MST algorithms like Prim's behave differently on disconnected graphs, finding a tree for only the component containing the start node.

  • Standard MST algorithms assume a connected graph and cannot form a single spanning tree if it is disconnected.
  • Prim's algorithm, starting from a source vertex, will only explore its connected component.
  • Vertices in other components are unreachable and will never be added to the resulting MST.
  • To handle this, the algorithm must be run on each component, creating a Minimum Spanning Forest (MSF).
Python: Prim's on a Single Component
1import heapq
2
3# A graph with two disconnected components: {A,B,C} and {D,E,F}
4graph = {
5    'A': {'B': 2, 'C': 4}, 'B': {'A': 2, 'C': 3}, 'C': {'B': 3, 'A': 4},
6    'D': {'E': 5, 'F': 6}, 'E': {'D': 5, 'F': 1}, 'F': {'E': 1, 'D': 6}
7}
8
9def prim_single_component(graph, start_node):
10    mst = []
11    visited = {start_node}
12    # (weight, from_vertex, to_vertex)
13    edges = [(w, start_node, neighbor) for neighbor, w in graph[start_node].items()]
14    heapq.heapify(edges)
15
16    while edges and len(visited) < len(graph):
17        weight, u, v = heapq.heappop(edges)
18        if v not in visited:
19            visited.add(v)
20            mst.append((u, v, weight))
21            for neighbor, w in graph[v].items():
22                if neighbor not in visited:
23                    heapq.heappush(edges, (w, v, neighbor))
24    return mst
25
26# Start Prim's from a vertex in the first component
27start_vertex = 'A'
28component_mst = prim_single_component(graph, start_vertex)
29
30print(f"Starting Prim's from vertex '{start_vertex}':")
31print(f"MST found: {component_mst}")
32print(f"Vertices reached: {sorted(list(set(v for e in component_mst for v in e[:2])) | {start_vertex})}")